package main

import "fmt"

/*
	消除游戏
给定一个从1 到 n 排序的整数列表。
首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。
第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。
我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
返回长度为 n 的列表中，最后剩下的数字。

示例：
输入:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
输出:
6
 */

/*
解题思路
1、如果n是奇数，那么假设n=2k+1
1）如果从左往右
1 2 3 4 5 6 ... 2k+1 ->
第一次消除后剩余
2 4 6 ... 2k <-
转换一下，类似于下面的消除，但是所有数字都是其两倍
1 2 3 ... k <-
所以，这种情况下，结果为
f(n/2, 相反方向) * 2

2、如果n是偶数，那么假设n=2k
1）如果从左向右
1 2 3 4 5 6 ... 2k ->
第一次消除后剩余
2 4 6 ... 2k <-
转换一下，类似于下面的消除，但是所有数字都是其两倍
1 2 3 ... k <-
所以，这种情况下，结果为
f(n/2, 相反方向) * 2

2）如果从右向左
1 2 3 4 5 6 ... 2k <-
第一次消除后剩余
1 3 5 ... 2k-1 ->
转换一下，类似于下面的消除，但是所有数字都加了1
2 4 6 ... 2k ->
再次转换一下，类似于下面的消除，但是所有数字都是其两倍
1 2 3 ... k <-
所以，这种情况下，结果为
f(n/2, 相反方向) * 2 - 1
*/

func lastRemaining(n int) int {
	return dfs(n, true)
}

func dfs(n int, fromLeft bool) int {
	if n == 1 {
		return 1
	}
	// 如果是奇数的话，从左从右都一样
	if n%2 == 1 {
		return 2 * dfs(n/2, !fromLeft)
	}
	// 如果是偶数,左右消除结果有区分
	if fromLeft {
		return 2 * dfs(n/2, !fromLeft)
	}
	return 2*dfs(n/2, !fromLeft) - 1
}


func main() {
	fmt.Println(lastRemaining(100))
}
